import numpy
import copy
import utl
import time


#定义数组下标
arrayWidth = 15
arrayHeigh = 15


#决策树类
#棋子模型  ,分数模型
#越复杂，系统越好，算力越大耗费资源越大

class matrixTool():        #矩阵工具类
	def __init__(self):
		#分数模型 ， 并且打分#  ,修改key值不会更新分数模型#########
		##ai分数评估模型
		
		self.aiGradeModel  = [
				# (5,(1,0,0,0,0)),  #30
				# (8,(0,1,0,0,0)),  #30
				# (8,(0,0,1,0,0)),  #30
				# (8,(0,0,0,1,0)),   #30
				# (5,(0,0,0,0,1)),   #30
				(30,(1,1,0,0,0)),  #30
				(80,(0,1,1,0,0)),
				(80,(0,0,1,1,0)),
				(30,(0,0,0,1,1)),
				(40,(1,0,1,0,0)),
				(40,(0,1,0,1,0)),
				(30,(0,0,1,0,1)),
				(30,(1,0,0,1,0)),
				(30,(1,0,0,0,1)),
				(30,(0,1,0,0,1)),
				(170,(1,1,1,0,0)), 
				(170,(0,0,1,1,1)),
				(575,(0,1,1,1,0)),
				(170,(1,0,1,1,0)), 
				(170,(0,1,0,1,1)),
				(130,(1,0,0,1,1)),
				(170,(1,1,0,1,0)),
				(170,(0,1,1,0,1)),       #70
				(2590,(0,1,1,1,1)),       #90
				(2590,(1,0,1,1,1)),
				(2590,(1,1,0,1,1)),
				(2590,(1,1,1,0,1)),
				(2590,(1,1,1,1,0)),
				(8400,(0,1,1,1,1,0)),    #100
				(1385,(0,0,1,1,1,0,0)),   #85
				(10000,(1,1,1,1,1))]      ##赢了200

		##人类分数评估模型
		self.manGradeModel  = [
				# (5,(2,0,0,0,0)),  #30
				# (8,(0,2,0,0,0)),  #30
				# (8,(0,0,2,0,0)),  #30
				# (8,(0,0,0,2,0)),   #30
				# (5,(0,0,0,0,2)),   #30
				(30,(2,2,0,0,0)),  #30
				(80,(0,2,2,0,0)),
				(80,(0,0,2,2,0)),
				(30,(0,0,0,2,2)),
				(40,(2,0,2,0,0)),
				(40,(0,2,0,2,0)),
				(30,(0,0,2,0,2)),
				(30,(2,0,0,2,0)),
				(30,(2,0,0,0,2)),
				(30,(0,2,0,0,2)),
				(170,(2,2,2,0,0)), 
				(170,(0,0,2,2,2)),
				(575,(0,2,2,2,0)),
				(170,(2,0,2,2,0)), 
				(170,(0,2,0,2,2)),
				(130,(2,0,0,2,2)),
				(170,(2,2,0,2,0)),
				(170,(0,2,2,0,2)),       #70
				(2590,(0,2,2,2,2)),       #90
				(2590,(2,0,2,2,2)),
				(2590,(2,2,0,2,2)),
				(2590,(2,2,2,0,2)),
				(2590,(2,2,2,2,0)),
				(8400,(0,2,2,2,2,0)),    #100
				(1385,(0,0,2,2,2,0)),   #85
				(10000,(2,2,2,2,2))]      ##赢了200


		self.callBreakFlag = 0    ##博弈树递归遍历中断设置
		self.treeDeep  =  3       ##博弈树的深度
		
		self.alpha_cut =  -10     ##剪枝参数（最小） ， 开始设置成无穷小
		self.beta_cut  =  100000    ##剪枝参数(最大) ,开始设置成无穷大

		self.travellCut = 0   ##数组遍历控制 1，中断

	##博弈树窗口函数（区间）
	##alpha ， beta 窗口

##优化方案，排序，及不计算没有邻居的点
	###博弈树算法#####
	###选择深度优先####
	###评估函数#######
	###极大值与极小值搜索#####
	###ai ---->取极大值 ， man---->去极小值
	##递归遍历矩阵
	####棋位分数计算函数####
	####目前问题，评估函数效率太低，导致计算量巨大
	##经过测试不是评估函数耗时最大，是求最大最小值函数耗时最大
	##极大极小搜索导致的耗时严重###
	###直接返回4，耗时45秒
	##必须优化评估函数
	###两种计算方案，新的计算方式只用一个函数完成，但是有乘法运算，
	##经测试，更耗时，但代码更简洁
	def evaluatePosGrade(self , array , x , y , flag ):
		if(array[x][y] != 0 ):  ##棋位不空
			return -1
		###矩阵的设置及分数模型的转换
		array[x][y] = flag    #设置矩阵的临时标志
		###进攻分数
		temp_x     = self.maxtrixDirectionLevelGrade( x , y, array , flag , self.getEvaluateGradeModelWithFlag(flag))  #x方向
		temp_y     = self.maxtrixDirectionVerticalGrade(  x , y, array , flag , self.getEvaluateGradeModelWithFlag(flag))  #y方向
		temp_left  = self.maxtrixDirectionLeftDiagonalGrade(  x , y, array , flag, self.getEvaluateGradeModelWithFlag(flag))  #x方向
		temp_right = self.maxtrixDirectionRightDiagonalGrade(  x , y, array , flag, self.getEvaluateGradeModelWithFlag(flag))  #y方向
		temp_last_grade =   temp_x + temp_y + temp_left + temp_right
		
		###防御分数
		array[x][y] = self.getOppositeFlag(flag)

		temp_xs     = self.maxtrixDirectionLevelGrade(  x , y, array , self.getOppositeFlag(flag) , self.getEvaluateGradeModelWithFlag(self.getOppositeFlag(flag)))  #x方向
		temp_ys     = self.maxtrixDirectionVerticalGrade(  x , y, array , self.getOppositeFlag(flag) ,self.getEvaluateGradeModelWithFlag(self.getOppositeFlag(flag)))  #y方向
		temp_lefts  = self.maxtrixDirectionLeftDiagonalGrade(  x , y, array , self.getOppositeFlag(flag) ,self.getEvaluateGradeModelWithFlag(self.getOppositeFlag(flag)))  #x方向
		temp_rights = self.maxtrixDirectionRightDiagonalGrade(  x , y, array , self.getOppositeFlag(flag), self.getEvaluateGradeModelWithFlag(self.getOppositeFlag(flag)))  #y方向
		temp_defend_grade = temp_xs + temp_ys + temp_lefts + temp_rights



		###设置防御机制
		# if(temp_defend_grade >1300):
		# 	temp_defend_grade = 99999999  ###设置为无穷大

		temp_last_grade = temp_last_grade + temp_defend_grade

		# gradeCalculate(self, x , y , x_dir , y_dir ,array , grade_model ):
		##x,y数组下标，x_dir,y_dir计算方向(1,0 )(0,1)(1,1)(1,-1)代表不同的方向
		#恒速撇捺
		# array[x][y] = flag    #设置矩阵的临时标志
		# temp_x = self.gradeCalculate(x , y , 1 , 0 ,array , self.getEvaluateGradeModelWithFlag(flag) )
		# temp_y = self.gradeCalculate(x , y , 0 , 1 ,array , self.getEvaluateGradeModelWithFlag(flag) )
		# temp_left = self.gradeCalculate(x , y , 1 , 1 ,array , self.getEvaluateGradeModelWithFlag(flag) )
		# temp_right =self.gradeCalculate(x , y , 1 , -1 ,array , self.getEvaluateGradeModelWithFlag(flag) )
		# temp_last_grade =   temp_x + temp_y + temp_left + temp_right


		# array[x][y] = self.getOppositeFlag(flag)

		# temp_xs = self.gradeCalculate(x , y , 1 , 0 ,array , self.getEvaluateGradeModelWithFlag(self.getOppositeFlag(flag)) )
		# temp_ys = self.gradeCalculate(x , y , 0 , 1 ,array , self.getEvaluateGradeModelWithFlag(self.getOppositeFlag(flag)) )
		# temp_lefts = self.gradeCalculate(x , y , 1 , 1 ,array , self.getEvaluateGradeModelWithFlag(self.getOppositeFlag(flag)) )
		# temp_rights =self.gradeCalculate(x , y , 1 , -1 ,array , self.getEvaluateGradeModelWithFlag(self.getOppositeFlag(flag)) )

		# temp_defend_grade = temp_xs + temp_ys + temp_lefts + temp_rights
		# temp_last_grade = temp_last_grade + temp_defend_grade
		
		array[x][y] = 0  ##重置标志
		return  temp_last_grade


###
##不是简单的博弈树
##需要抽象话五子棋，转化唔博弈树
###已做alpha ,beta 裁剪，
###需要做一个后续遍历，深度优先
##alpha值与beta值设置有问题，需要在同一层的节点使用
##参数添加alpha，beta参数 ,
##解决方法，直接传递alpha，beta参数即可


###继续优化方案:剪更多的枝，如进行排序，
##剪更多的枝，
##剪更多的枝，
##剪更多的枝，
	def gameTreeTravell(self, array , flag   , alpha, beta , deep  ):
		if(deep <= 0 ):  ##博弈树树到底层了,返回
			return None
		is_loop_break = 0  ##0表示循环正常 ， 1循环中断 # 循环控制 标志
		score_list  = numpy.zeros((arrayWidth,arrayHeigh))  #定义一个分数表
		temp_max_value = 0        #最大值
		temp_min_value = 100000

		index_x = 0 
		index_y = 0
	
		for x  in range(array.shape[0] ):
			if(is_loop_break):   ####循环中断开关
				print("剪枝中........外层剪枝")
				break
			for y  in range(array.shape[1]):
				if(array[x][y] != 0 ):  ###该位置不可操作
					continue
				#附近节点空，则不计算，减少计算量
				if( self.isNextStepNull(x , y ,array)):
					continue
				if(deep == 1):  ###叶节点时，才计算值，极大值搜索，大于beta值，减去
					# t0 = time.perf_counter()
					grade = self.evaluatePosGrade(array , x, y , flag)
					# print("evaluatePosGrade函数耗时:",time.perf_counter() - t0)
					score_list[x][y] = grade 
					##求最大值
					if(grade > temp_max_value):
						temp_max_value = grade
						index_x = x 
						index_y = y
					##求最大值
					##剪枝处理
					if(grade >= beta ):
						print("****************************")
						print("beta剪枝中.... deep = ",deep)
						print("alpha = ",alpha)
						print("beta = ",beta)
						print("grade = ",grade)
						print("****************************")
						is_loop_break = 1
						break    ##要break 两层
					##剪枝处理
				else:  ##deep不等于1时候
					###进入递归循环###
					##重置标志
					array[x][y] = flag
					return_grade_list ,temp_max_value ,index_x ,index_y , temp_min_value = \
					self.gameTreeTravell(array ,self.getOppositeFlag(flag) ,  alpha , beta , deep - 1)
					array[x][y] = 0
					if(deep == 2):
						score_list[x][y] = temp_max_value
						##剪枝  ,开始，beta_cut 无穷大，不可能小于max_value
						##设置beta，滑动窗口
						if(temp_max_value < beta):
							beta = temp_max_value
							print("beta 设置中, beta = ",beta)
							print("alpha = ",alpha)
							print("beta = ",beta)
							print("############################")
						if(temp_max_value <= temp_min_value):  ##第二层选最小值
							temp_min_value = temp_max_value
						###设置剪枝####
						##alpha开始负无穷，不可能大于max_value
						if(temp_max_value <= alpha):  ##与beta对应
							print("############################")
							print("alpha剪枝中.... deep = ",deep)
							print("temp_max_value = ",temp_max_value)
							print("alpha = ",alpha)
							print("beta = ",beta)
							print("############################")
							is_loop_break = 1
							break    ##要break 两层
						###设置剪枝####		
					elif(deep == 3):  ##第一层节点，极大值搜索
						score_list[x][y] = temp_min_value
						if(temp_min_value >= alpha):
							alpha = temp_min_value
							print("alpha值设置 alpha= ",alpha)
							print("alpha = ",alpha)
							print("beta = ",beta)
							print("deep = ",deep)
					array[x][y] = 0
				array[x][y] = 0  ###重置标志		
		return score_list,temp_max_value ,index_x , index_y,temp_min_value 


###博弈树#####
###博弈树循环有问题，导致裁剪不方便#####
###博弈树里面双层for循环导致不能有效裁剪#####
	##附近节点是否走过
	def isNextStepNull(self, x , y , array ):
		for i in range(-1, 2):
			for j in range(-1, 2):
				if (i == 0 and j == 0 ):
					continue
				if( x + i < 0 or y + j < 0 or x + i > array.shape[0]-1 or y + j >array.shape[1]-1):
					continue
				if(array[x + i][y + j] != 0):
					return False
		return True

	####返回计算的位置######
	def getAiIndex(self, array , flag , deep ):
		#调用评估函数#
		#初始化剪枝区间滑动窗口
		alpha =  -10     ##剪枝参数（最小） ， 开始设置成无穷小
		beta  =  100000    ##剪枝参数(最大) ,开始设置成无穷大
		pos = utl.pos()
		t0 = time.perf_counter()
		list1 , max , pos.x ,pos.y ,min = self.gameTreeTravell( array , flag   , alpha , beta ,  deep )
		print("获取ai棋位耗时:",time.perf_counter() - t0)
		return pos

	def maxtrixDirectionLeftDiagonalGrade(self, x,y , array , flag , grade_model):   #左对角线方向
		shape_pos = []  #分数模型数组
		i = 0
		score_list = [] #匹配的分数list
		last_score = 0 #最后的分数

		begin_x  = x - 4    #初始化边界
		begin_y  = y - 4
		while(begin_x <=  x + 4):
			if(begin_x < 0 or begin_y < 0 ):   #越界情况
				begin_x = begin_x + 1 
				begin_y = begin_y + 1
				continue

			if (begin_x > array.shape[0] - 1 or begin_y > array.shape[1] - 1):
				break
			shape_pos.append(array[begin_x][begin_y])
			# print("打印我的积累模型：",shape_pos)
			if (i == 4):
				tmp_shape_5 = tuple(shape_pos)
				tmp_shape_6 = shape_pos
				if(begin_x + 1 <array.shape[1] and begin_y + 1 < array.shape[0]):
					tmp_shape_6.append(array[begin_x+1][begin_y+1])
				for (score, shape) in grade_model :
					if (shape == tmp_shape_5 or shape == tuple(tmp_shape_6)):
						if(score > last_score):
							last_score = score
				begin_x = begin_x - 4
				begin_y = begin_y - 4
				shape_pos = []  #清空元组
				i = -1
			begin_x = begin_x + 1
			begin_y = begin_y + 1
			i = i + 1
		return last_score
	
	def maxtrixDirectionRightDiagonalGrade(self, x,y , array ,flag ,grade_model):   #右对角线方向
		shape_pos  = []            #分数模型数组
		score_list = []           #匹配的分数list
		last_score = 0            #最后的分数
		begin_x  = x - 4    #初始化边界 ，循环索引
		begin_y  = y + 4
		i = 0

		while(begin_x <= x + 4 ):
			if(begin_x < 0 or begin_y >= array.shape[1] ):    #循环始坐标数组处理
				begin_x = begin_x + 1
				begin_y = begin_y - 1 
				continue
			if(begin_x > array.shape[0] - 1 or begin_y < 0 ): #越界处理
				break
			shape_pos.append(array[begin_x][begin_y])
			if (i == 4):
				tmp_shap_5 = tuple(shape_pos)
				tmp_shap_6 = shape_pos
				
				if(begin_x + 1 < array.shape[1] and begin_y - 1 > 0 ): #不越界
					tmp_shap_6.append(array[begin_x + 1 ][begin_y - 1])
				for (score, shape) in grade_model :
					if (shape == tmp_shap_5 or shape == tuple(tmp_shap_6)):
						if(score > last_score):
							last_score = score
				begin_x = begin_x - 4
				begin_y = begin_y + 4
				shape_pos = []  #清空元组
				i = -1
			begin_x = begin_x + 1
			begin_y = begin_y - 1
			i = i + 1
		return last_score

	def maxtrixDirectionLevelGrade(self, x  , y , array , flag , grade_model ):   #水平方向
		shape_pos = []  #分数模型数组
		i = 0
		score_list = [] #匹配的分数list
		last_score = 0 #最后的分数
		begin  = y - 4
		while(begin <= y + 4 ):
			if(begin < 0  ):         #越界情况
				begin = begin + 1
				continue
			if(begin > array.shape[1] - 1 ):    #越界情况
				break
			shape_pos.append(array[x][begin])
			if (i == 4):
				tmp_shap_5  = tuple(shape_pos)            ##5棋位于6棋位的判断
				tmp_shap_6  = shape_pos

				if(begin + 1 <= array.shape[1] - 1):
					tmp_shap_6.append(array[x][begin + 1])
				for (score, shape) in grade_model :
					if ((shape == tmp_shap_5) or (shape == tuple(tmp_shap_6))):
						if(score > last_score):
							last_score = score
				begin = begin - 4      #判断循环是否中断
				shape_pos = []  #清空元组
				i = -1
			begin = begin + 1
			i = i + 1
		return last_score

	
    ###返回该点的最高分数######
	def maxtrixDirectionVerticalGrade(self , x,y , array ,flag ,grade_model ): #打分 ,根据矩阵匹配分数
		begin = x - 4  #遍历的开始下标
		shape_pos  = []      #分数模型数组
		score_list = []      #匹配的分数list
		last_score = 0       #最后的分数
		i = 0
		while (begin <= x + 4 ):                #数组的x方向，相当于坐标的y轴
			if(begin < 0 ):                           ##数组越界考虑
				begin = begin + 1
				continue
			if(begin >= array.shape[0]):              ##数组越界，中断循环
				break
			shape_pos.append(array[begin][y])   ##构造分数模型###
			if (i == 4): 
				tmp_shap_5  = tuple(shape_pos)        ##list 转元组
				# tmp_shap_6  = copy.deepcopy(shape_pos)
				tmp_shap_6  = shape_pos
				
				if(begin + 1 <= array.shape[1] - 1):  #构造6棋子情况
					tmp_shap_6.append(array[begin + 1 ][y])  

				for (score, shape) in grade_model :
					if (shape == tmp_shap_5 or shape == tuple(tmp_shap_6)):
						# print("找到分数模型：",shape_pos)
						if(score > last_score):
							last_score = score
				begin = begin - 4      #判断循环是否中断
				shape_pos = []  #清空元组
				i = -1
			begin = begin + 1
			i = i + 1
		return last_score	


	#@返回相反的标志 flag = 1返回2
	def getOppositeFlag(self , flag):
		if (flag == 1):
			return 2
		else:
			return 1

    ##返回is_ai的反向标志 ，1代表是ai， 0代表不是ai(人类)
	def getOppositeAiFlag(self , is_ai):
		return not is_ai

	##根据flag 及ai 返回队友分数评估模型
	def getEvaluateGradeModelWithFlag(self, flag ):
		if (flag == 1):
			return self.aiGradeModel
		else:
			return self.manGradeModel
		assert("评估分数模型返回失败！！！！")


###通过一个for循环，计算各个方向的分数并叠加
###构造一个通用的计分函数
###x,y数组下标，x_dir,y_dir,（0,1 表示横向， 1，0 表示竖向 ， ）遍历的方向
##array遍历的数组 ，grade_model查找的分数模型
##经过测试，比老版的慢了近一分钟，原因是进行了大量的乘法运算

###目前，效率较低目前的运算量，低了近60秒####
	def gradeCalculate(self, x , y , x_dir , y_dir ,array , grade_model ):   #水平方向
		last_score = 0 #最后的分数
		for offset in range(-5 , 1):  ###通过一个双层循环，定义一个
			shape_pos = []			 ##左右遍历的环境6*6次计算量
			for value in range(0 , 6):
				tem_x = x + (value + offset) * x_dir
				tem_y = y + (value + offset) * y_dir
				if(tem_x>= 0 and tem_y>=0 and \
					tem_x< array.shape[0]- 1 and tem_y< array.shape[1]- 1):
					shape_pos.append(array[tem_x][tem_y])
				else:
					shape_pos.append(-1) ##特殊情况搞个 -1标志
			tmp_shap5 = (shape_pos[0], shape_pos[1], shape_pos[2], shape_pos[3], shape_pos[4])
			tmp_shap6 = (shape_pos[0], shape_pos[1], shape_pos[2], shape_pos[3], shape_pos[4], shape_pos[5])
			for (score, shape) in grade_model :
				if ((shape == tmp_shap5) or (shape == tmp_shap6)):
					if(score > last_score):
						last_score = score
		return last_score

	





